package indi.caspar.algorithms;

/**
 * Created by casparhuan on 2017/3/5.
 */
public class Solution {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }


    public static void main(String[] args) {
        Solution so = new Solution();
        so.reConstructBinaryTree(new int[]{1,2,4,7,3,5,6,8},new int[]{4,7,2,1,5,3,8,6});
    }
    private TreeNode reConstructBinaryTree(int[] pre,int preStartIndex,int preEndIndex,
                                           int[] in ,int inStartIndex,int inEndIndex){
        if(preEndIndex - preStartIndex != inEndIndex - inStartIndex){
            return null;
        }
        TreeNode root = new TreeNode(pre[preStartIndex]);
        int rootIndexInArr = -1;
        if(preStartIndex == preEndIndex){
            return root;
        }

        //寻找中序遍历中的位置
        for(int i = inStartIndex ;i <= inEndIndex ; i++){
            System.out.println("111:"+inStartIndex);
            if( in[i] == root.val){
                rootIndexInArr = i;
                break;
            }
        }
        if(rootIndexInArr == -1 ){
            return null;
        }
        int leftTreeLength = rootIndexInArr - inStartIndex;

        if(leftTreeLength != 0){
            root.left = reConstructBinaryTree(pre,preStartIndex + 1 , preStartIndex + 1   + leftTreeLength - 1 ,
                    in , inStartIndex, inStartIndex + leftTreeLength -1);//rootIndexInArr - 1
        }
        int rightTreeLength = inEndIndex - rootIndexInArr;
        if(rightTreeLength != 0){
            root.right = reConstructBinaryTree(pre,preEndIndex - rightTreeLength + 1 ,preEndIndex,
                    in , inEndIndex - rightTreeLength + 1 , inEndIndex);
        }
        return root;
    }

    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        return reConstructBinaryTree(pre, 0 , pre.length - 1 , in , 0 , in.length-1);
    }

}
